/**
 * java中的链表
 * @author smallcatX0 
 * @date    2018-01-14 17:16:11
 * @version $Id$
 * 非递归方法未解决 
 */

public class linkTest {
    public static void main(String[] args) {
        // System.out.println();
        Link l1 = new Link();
        l1.add(12);
        l1.add(55);
        l1.add(5);
        l1.add(15);  
        l1.add(2.45);
        l1.add("asd"); // 增
        System.out.println("初始化："+l1);
        l1.remove(5);  // 删
        System.out.println("删除某个节点： "+l1);
        l1.set(0,99);  // 改
        System.out.println("更新某个节点： "+l1);
        System.out.println("查找第三个："+l1.get(2));
    }
}
class Link{
    // ================内部类======================= //
    private class Node{
        private Object data;
        private Node next;
        public Node(Object data){
            this.data = data;
            this.next = null;
        }
        /**
         * 添加新节点（尾插）
         * @Author   smallcatX0
         * @DateTime 2018-01-14
         * @Email    smallcatX0@gmail.com
         * @param    newNode              新节点（Node）
         */
        public void addNode(Node newNode){
            if (this.next == null) {   // 当前节点的下一个节点为空
                this.next = newNode;   // 当前节点为尾节点 直接加在后面
            }else{    // 递归找到尾节点
                this.next.addNode(newNode);
            }
        }
        /**
         * 判断节点链中是否存在某一个数据
         * @Author   smallcatX0
         * @DateTime 2018-01-14
         * @Email    smallcatX0@gmail.com
         * @param    data                 任意对象（Object）
         * @return                        存在（true）/不存在（false）
         */
        public boolean containsNode(Object data){
            if (data.equals(this.data)) {     // 当前节点的值与形参相等
                return true;                  // 返回找到
            }
            else{                             // 否则递归到尾节点
                if (this.next != null ) {
                    return this.next.containsNode(data);
                } else{
                    return false;             // 到尾节点都没找到 返回false
                }
            }
        }
        /**
         * 将节点集转化为数组
         * @Author   smallcatX0
         * @DateTime 2018-01-15
         * @Email    smallcatX0@gmail.com
         */
        public void toArrayNode(){
            Link.this.reArr[ Link.this.foot++ ] = this.data;  //当前数据保存在数组中
            if (this.next != null) {   // 递归到尾节点
                this.next.toArrayNode(); 
            }
        }
       
        /**
         * 修改索引节点的数据
         * @Author   smallcatX0
         * @DateTime 2018-01-15
         * @Email    smallcatX0@gmail.com
         * @param    i                    节点索引（int）
         * @param    data                 节点数据（Object）
         */
        public void setNode(int i,Object data){
            if (Link.this.foot++ == i) { // 判断指针是否等于索引值，随后指针加一
                this.data = data;        // 是索引值则修该当前节点数据
            }else { // 递归调用次方法，知道找到索引的节点
                this.next.setNode(i,data);
            }
        }
        /**
         * 查找删除
         * @Author   smallcatX0
         * @DateTime 2018-01-15
         * @Email    smallcatX0@gmail.com
         * @param    p                    当前节点的上个节点（Node）
         * @param    data                 待查删除的数据
         */
        public void removeNode(Node p,Object data){
            if (data.equals(this.data)) {
                p.next = this.next;
            }else {
                this.next.removeNode(this,data);
            }
        }
        /**
         * 获取索引的节点数据
         * @Author   smallcatX0
         * @DateTime 2018-01-15
         * @Email    smallcatX0@gmail.com
         * @param    i                    
         * @return                        节点的数据（Object）
         */
        public Object getNode(int i){
            if (Link.this.foot++ == i)  return this.data; 
            else return this.next.getNode(i) ;
        }
    }
    // ============= 以上是内部类 =============//
    private Node root ;     // 根节点
    private int count = 0;  // 保存元素个数
    private int foot  = 0;  // 节点索引
    private Object [] reArr ;// 返回的数组
    /**
     * 链表的添加（尾追）
     * @Author   smallcatX0
     * @DateTime 2018-01-14
     * @Email    smallcatX0@gmail.com
     * @param    data                 任意对象（Object）
     */
    public void add(Object data){
        if (data == null) {  
            return ;      // 不允许添加NULL
        }
        Node newNode =new Node(data);
        if (this.root == null) {      // 根节点为空
            this.root = newNode;      // 直接添加到根节点上
        }else {     // 根节点存在 交给Node类的addNode()解决
            this.root.addNode(newNode);
        }
        this.count ++; // 添加成功,长度加一
    }
    /**
     * 判断某个数据是否在链表中
     * @Author   smallcatX0
     * @DateTime 2018-01-15
     * @Email    smallcatX0@gmail.com
     * @param    data                 查找的数据（Object）
     * @return                        存在（true）、不存在（false）
     */
    public boolean contains(Object data){
        if (data == null || this.root == null) {
            return false;
        }
        return this.root.containsNode(data);
    }
    /**
     * 删除某个节点
     * @Author   smallcatX0
     * @DateTime 2018-01-15
     * @Email    smallcatX0@gmail.com
     * @param    data                 待删除的数据（Object）
     */
    public void remove(Object data){
        if (this.contains(data)) {         // 判断待删数据是否存在
            if (data.equals(this.root.data)) {  // 如果待删数据就是头结点
                this.root = this.root.next;     // 删除头结点
            } else {  // 交给Node类的removeNode()处理
                this.root.next.removeNode(this.root,data);
            }
            this.count --;
        }
    }
    /**
     * 根据索引修改某节点
     * @Author   smallcatX0
     * @DateTime 2018-01-15
     * @Email    smallcatX0@gmail.com
     * @param    i                    索引值（int）
     * @param    data                 更新的数据（Object）
     */
    public void set(int i,Object data){
        if (i < 0 || i > this.count) return ;   // 判断索引是否越界
        this.foot = 0;  // 指针归零
        this.root.setNode(i,data); // 调用Node的setNode()方法处理
    }
    /**
     * 根据索引查找链表中的数据
     * @Author   smallcatX0
     * @DateTime 2018-01-15
     * @Email    smallcatX0@gmail.com
     * @param    i                    索引值（int）
     * @return                        节点的数据（Object）
     */
    public Object get(int i){
        if (i < 0 || i > this.count) return null;   // 判断索引是否越界
        this.foot = 0;  //指针归零
        return this.root.getNode(i); // 交给Node类的getNode()处理
    }
    /**
     * 清空链表
     * @Author   smallcatX0
     * @DateTime 2018-01-15
     * @Email    smallcatX0@gmail.com
     */
    public void clear(){
        this.root  = null;
        this.count = 0;
    }
    public boolean isEmpty(){
        return this.count == 0;
    }
    public int size(){
        return this.count;
    }
    /**
     * 以数组返回链表的数据
     * @Author   smallcatX0
     * @DateTime 2018-01-14
     * @Email    smallcatX0@gmail.com
     * @return   Object[] 对象数组
     */
    public Object [] toArray(){
        if (this.root == null)  return null; // 如果根节点为空,返回空
        this.foot = 0;           // 游标归零
        this.reArr = new Object [this.count];  
        this.root.toArrayNode();   // 交给 Node类的toArrayNode()处理
        return this.reArr;     
    }
    /**
     * 覆写toString方法 将链表中所有的数据以字符串输出
     * @Author   smallcatX0
     * @DateTime 2018-01-14
     * @Email    smallcatX0@gmail.com
     * @return   字符串（String）
     */
    public String toString(){
        String res ="";  
        this.toArray();  // 将链表数据先转化为数组
        for (Object i : this.reArr ) {
            if (i != null ) {  // 将其中每一个转化为字符串并追加到后面
                res = res + i.toString() +" ";  
            }
        }
        return res;
    }

}